2012/01/17

Recent entries from same category

  1. RapidJSON や simdjson よりも速いC言語から使えるJSONライブラリ「yyjson」
  2. コメントも扱える高機能な C++ 向け JSON パーサ「jsoncpp」
  3. C++ で flask ライクなウェブサーバ「clask」書いた。
  4. C++ 用 SQLite3 ORM 「sqlite_orm」が便利。
  5. zsh で PATH に相対パスを含んだ場合にコマンドが補完できないのは意図的かどうか。

trieなんたらが話題になってたのでなんとなく書いてみた。
ベンチとかはやってない。
404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン?

そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列( Associative array )がコレクション( Collection )、すなわち数多のデータ構造をまとめるデータ構造としての覇...

http://blog.livedoor.jp/dankogai/archives/51765855.html
#include <stdio.h>
#include <stdlib.h>

typedef struct _trie {
  char c;
  unsigned int n;
  struct _trie** next;
  void* value;
} trie;

trie*
trie_new() {
  trie* p = (trie*) malloc(sizeof(trie));
  p->c = 0;
  p->n = 0;
  p->next = NULL;
  return p;
}

void
trie_free(trie* p) {
  unsigned int i;
  for (i = 0; i < p->n; i++)
    trie_free(p->next[i]);
  if (p->n)
    free(p->next);
  free(p);
}

trie*
trie_put(trie* p, const char* key, const void* value) {
  if (*key == 0) {
    p->value = (void*) value;
    return p;
  }
  trie* next = NULL;
  int i;
  for (i = 0; i < p->n; i++)
    if (p->next[i]->c == *key) {
      next = p;
      break;
    }
  if (!next) {
    if (!(next = trie_new())) return NULL;
    trie** children = (trie**) realloc(p->next, p->n * sizeof(trie*));
    if (!children) return NULL;
    p->next = children;

    next->c = *key;
    p->next[p->n] = next;
    p->n++;
  }
  return trie_put(next, key+1, value);
}

trie*
trie_get(trie* p, const char* key) {
  if (p->c) {
    if (p->c != *key)
      return NULL;
    if (p->c == *key && *(key+1) == 0)
      return p;
    key++;
  }
  int i;
  trie* value = NULL;
  for (i = 0; i < p->n; i++) {
    if ((value = trie_get(p->next[i], key)))
      return value;
  }
  return NULL;
}

void
safe_puts(const char* key, const trie* p) {
  if (!p)
    printf("%s not found\n", key);
  else if (!p->value)
    printf("%s: null\n", key);
  else
    printf("%s%s\n", key, (char*) p->value);
}

int
main(int argc, char* argv[]) {
  trie* p = trie_new();
  trie* v;

  trie_put(p, "foo""bar");
  trie_put(p, "bar""baz");

  v = trie_get(p, "baz");
  safe_puts("baz", v);

  v = trie_get(p, "foo");
  safe_puts("foo", v);

  v = trie_get(p, "bar");
  safe_puts("bar", v);

  trie_put(p, "うんこ""うんこっこー");
  v = trie_get(p, "うんこ");
  safe_puts("うんこ", v);

  v = trie_get(p, "404 blog");
  safe_puts("404 blog", v);

  trie_free(p);
  return 0;
}
baz not found
foo: bar
bar: baz
うんこ: うんこっこー
404 blog not found
Posted at by